92334 - 신고 결과 받기

info

• 문제 보기: 92334 - 신고 결과 받기
• 소요 시간: 22분 25초
• 풀이 언어: java
• 체감 난이도: 2️⃣
• 리뷰 횟수: ✅

풀이 키워드

스포주의

해시 자료구조

풀이 코드

info

• 메모리: 172000 KB
• 시간: 143 ms

import java.util.*;

class Solution {
    public int[] solution(String[] id_list, String[] report, int k) {
        Map<String, Set<String>> reporterMap = new HashMap<>();
        Map<String, Integer> mailCntMap = new HashMap<>();
        
        // init
        for (String id : id_list) {
            reporterMap.put(id, new HashSet<>());
            mailCntMap.put(id, 0);
        }
        
        // collect report
        for (String r : report) {
            String[] rArr = r.split(" ");
            String from = rArr[0];
            String to = rArr[1];
            Set<String> fromSet = reporterMap.get(to); // shallow copy
            if (fromSet.contains(from)) continue; // 'from' should be unique
            fromSet.add(from);
        }
        
        // send mail
        for (Map.Entry<String, Set<String>> e : reporterMap.entrySet()) {
            Set<String> fromSet = e.getValue();
            int reportCnt = fromSet.size();
            if (reportCnt < k) continue;
            for (String from : fromSet) {
                mailCntMap.merge(from, 1, Integer::sum);
            }
        }
        
        // count
        int[] ans = new int[id_list.length];
        for (int i = 0; i < id_list.length; ++i) {
            ans[i] = mailCntMap.get(id_list[i]);
        }
        return ans;
    }
}

풀이 해설

다음의 로직으로 풀이했다.

---

1. 피신고자(to) 해시 버킷에 신고자(from)들을 저장한다.
2. 피신고자 해시맵 entry를 순회하며 k 이상이면 신고자 해시 버킷에 메일 발송 횟수를 +1한다.
3. id_list를 순회하며 신고자 해시맵에서 메일 발송 횟수를 가져온다.

---

문제에서 신고는 한 사람에 대해 한번씩만 인정한다고 했으므로,
피신고자 해시맵에서의 신고자들은 List보다 Set으로 관리하는 것이 좋다.

Set이 해시 기반 구현이기에 contains 판별이 거의 $O(1)$이기 때문이다.

List와 Set의 퍼포먼스 비교

두 자료구조가 어느 정도의 차이를 보이는지 시각화해보자.

	TC 1	TC 2	TC 3	TC 4	TC 5	TC 6	TC 7	TC 8	TC 9	TC 10	TC 11	TC 12	TC 13	TC 14	TC 15	TC 16	TC 17	TC 18	TC 19	TC 20	TC 21	TC 22	TC 23	TC 24
List<String>	0.64	0.89	516.72	0.78	1.09	6.03	11.05	11.96	133.55	119.38	307.29	4.58	2.24	98.62	136.77	1.43	2.06	2.34	3.20	106.84	159.77	0.51	1.06	0.16
Set<String>	0.54	0.70	143.56	0.82	0.68	4.14	9.35	11.34	79.27	73.48	120.98	1.56	1.53	73.78	107.17	1.89	1.74	3.07	2.87	100.80	118.18	0.56	0.56	0.11

예상 범주 내에서 격차가 벌어지는 것을 확인할 수 있다.

contains에 대해 List<String>은 $O(n)$, Set<String>은 평균 $O(1)$의 시간복잡도를 지니므로,

// collect report
for (String r : report) {
    String[] rArr = r.split(" ");
    String from = rArr[0];
    String to = rArr[1];
    Set<String> fromSet = reporterMap.get(to); // shallow copy
    if (fromSet.contains(from)) continue; // 'from' should be unique
    fromSet.add(from);
}

효율성은 대부분 하이라이트한 코드 라인에서 차이가 발생하게 된다.

메모

• value에 List나 Set 들어가는 점에서 자바 해시맵 연습하기 아주 좋은 문제이다.
  • 여기서 한두술 정도 더 뜨면 그게 최신 코테 실전 문제 ㅇㅅㅇ